package com.lsa.letcode.the28.strstr;

public class Solution {
    public int strStr(String haystack, String needle) {
    	if (haystack.length() < needle.length()) {
    		return -1;
    	}
    	if (needle.length() == 0) {
    		return -1;
    	}
    	
    	int hashH = 0;
    	int hashN = 0;
    	
    	int power = 1;
    	for (int i = 0; i < needle.length(); i++) {
    		if (i > 0) {
    			power *= 10;
    		}
			
			hashN = hashN * 10 + needle.charAt(i);
			hashH = hashH * 10 + haystack.charAt(i);
		}
    	
    	// PRE : hashN is hash of needle
    	// PRE : hashH is hash of haystack[0 .. needle.len - 1]
    	
    	int i;
    	for (i = needle.length(); i < haystack.length(); i++) {
			if (hashN == hashH) {
				int j;
				for (j = i - needle.length(); j < i; j++) {
					if (needle.charAt(j - i + needle.length()) != haystack.charAt(j)) {
						break;
					}
				}
				if (j == i) {
					return i - needle.length();
				}
			}
			else {
				int hFirst = haystack.charAt(i - needle.length());
				hashH = (hashH - hFirst * power) * 10 + haystack.charAt(i);
			}
		}
    	
    	if (hashN == hashH) {
			int j;
			for (j = i - needle.length(); j < i; j++) {
				if (needle.charAt(j - i + needle.length()) != haystack.charAt(j)) {
					break;
				}
			}
			if (j == i) {
				return i - needle.length();
			}
		}
    	
        return -1;
    }
}